package com.zxy.leetcode._00100_00199._00130_00139;

/**
 * https://leetcode-cn.com/problems/single-number-ii/
 *
 * 137. 只出现一次的数字 II
 *
 * 标签：位运算
 */
public class Test00137 {

    public static void main(String[] args) {
        Test00137 test = new Test00137();
        int[] nums1 = {0, 1, 0, 1, 0, 1, 99};
        System.out.println(test.singleNumber(nums1));

        int[] nums2 = {2, 2, 2, -2147483648};
        System.out.println(test.singleNumber(nums2));
    }

    public int singleNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        // 为了应付负数
        long base = Integer.MAX_VALUE + 1L;
        int[] bits = new int[Long.SIZE];
        for (int num : nums) {
            int i=0;
            long n = base + num;
            while (n > 0) {
                bits[i] += n % 2;
                n = n >> 1;
                i ++;
            }
        }

        /*
         由于重复是3个，但如果直接对3取模，不重复那个是3的倍数就会返回0了，
         所以用每一位累加后对3取模，剩下的就是不重复的了
          */
        long result = 0;
        for (int i=0; i<bits.length; i++) {
            bits[i] = bits[i] % 3;
            if (bits[i] > 0) {
                result += bits[i] << i;
            }
        }

        return (int) (result - base);
    }

    // 官方解题方法2
    public int singleNumber2(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int total = 0;
            for (int num: nums) {
                total += ((num >> i) & 1);
            }
            if (total % 3 != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }

    // 官方解题方法3
    public int singleNumber3(int[] nums) {
        int a = 0, b = 0;
        for (int num : nums) {
            int aNext = (~a & b & num) | (a & ~b & ~num), bNext = ~a & (b ^ num);
            a = aNext;
            b = bNext;
        }
        return b;
    }

    // 官方解题方法4
    public int singleNumber4(int[] nums) {
        int a = 0, b = 0;
        for (int num : nums) {
            b = ~a & (b ^ num);
            a = ~b & (a ^ num);
        }
        return b;
    }

}
